\section{System Description}
This section of the report details the operations and purpose of the inf
The system consists of three independent parts:
\begin{enumerated}
\item The CAPTCHA system which has been given the working title of \textbf{KAPTCHA}, with the K signifying the surname of its creator.  It provides a mechanism 
\item
\item
\item
\end{enumerated}
The CAPTCHA system, the labelling game which provides labelled images and a collector of images.  The system has been given  

%the encorporation of human intelliegence into computer systems.


\subsection{Collection of Images}\label{subsec_collectionimages}
To provide a collection of images we utilised Google Images. To provide large numbers of images this processes was automated.  An API which would automate the querying process and download the resulting images was created.  This was done to gain a wide range of images as well as to demonstrate that the system could be implemented on a larger scale.  To provide the queries for the system a pre-processed version of the standard Linux dictionary was utilised.  The most frequent words were removed from the dictionary.  This was done through the use of a stopwords list, which contains the most frequently used terms in the English language. These words provide the least amount of meaning to the English language\cite{ir}.  The stopwords list used can be found as part of the  Terrier search engine \footnote{\url{http://ir.dcs.gla.ac.uk/terrier/Download.html}} stopword list.  Other criteria for removal from the dictionary included: People's names, places as well as company names. This was necessary to ensure that images met the following criteria:
\begin{itemize}
\item it did not contain explicit material which would be unsuitable for viewing and offend users. 
\item did not infringe copyright right laws, this is done to make sure that the university does not become liable for the use of trademarked images in its products.
\item the content of the image be unambiguous.  This is to ensure that users can not confuse the contents of the image and thus providing unrelated labels for the same image. 
\end{itemize}
Ultimately it was discovered that an additional manual search of the images was required to guarantee that the criteria could be met. Despite all queries being conducted with the strictest level of filtering, it was found that this was not always accurate.  The query used  can not be used as a term as it is unclear as to how that term was associated. It is possible that the term was generated from the surrounding text and, as such, should be discounted.  


% http://www.tex.ac.uk/tex-archive/macros/latex/contrib/algorithm2e/
% A comprehensive human computation framework: with application to image labelling
\subsection{General Description of Image labelling Game}\label{subsec_generatelabels}


The main problem with the use of complex images in KAPTCHA, that of automating associating the image term association. By presenting the problem in the form of a game, which is fun and where users can compete against each other for prizes, this would provide the KAPTCHA with enough labelled images to provide enough instances of the KAPTCHA to provide security.

The design of the game is based on Google Image Labeler\footnote{\url{http://images.google.com/imagelabeler/}} and Gwap \footnote{\url{http://www.gwap.com/gwap/}}  The project does not have the resources in money and time to target and exploit a large user base.  We limited the potential user base to that of the level three and four students in the department.  Both Google Image Labeler and Gwap required two players, in which two players are randomly assigned to each and given a series of images in which the two players have to agree upon a label which would represent the image. 


To make the game more challenging, the game set a series of labels which the user's are not able to enter called taboo words.  This ensures that images are associated with a wide variation of labels.  The users scores are calculated by how many attempts the users needed to agree upon a label for an image.  As our user base is small (roughly 148 potential users), it could not be guaranteed that there would be enough players at any one time to fulfil the requirement that two players would want to play the game.  It was also probable that due to users being confined to a small geographic area, that there was significant potential for users to collude and so increase their score.


The solution was to create a single player version of the game.  From the player’s perspective, the goal of the game is to provide a label which would answer the question "What would other people say about this image?"  The user is presented with an image and a series of, Taboo Words to provide the same mechanism as that used in the the Gwap and Google Labeler.  The user has to decide on a label which is not in the taboo words list but still meets the requirement that it describes the image.  The taboo words are generated from the frequencies of previous inputs into the system.  The score is determined by the level of agreement between the players.  The more terms a user has that are the same as other players, the greater the score. We surmise that the behaviour of the players will be consistent with the principal of least effort \cite{principleffort}  this is due to the most obvious label which can be assigned to an image is likely to be chosen by other users of the game.  A user will tend to choose these labels as they will earn more points for labels which have been agreed upon by other users of the game. When labelling an image, some users will have more taboo words than another user labelling the same image. This mechanism is designed to award users more points for the successful labelling of more challenging. The mechanism is designed provide a fair score, more points are awarded to a user who entered agreed terms which have more taboo words.  It also serves the purpose of encouraging users to provide a more varied set of labels for an image.  Due to the user base being known this allowed for the use of the University log-in information and thus any input would not be anonymous.  This information would be used to monitor user conduct and provide the ability to ban users who are colluding with one another to increase their score or by adding large number of in appropriate terms in an attempt to have them reach a significant number, which would allow the terms to appear as a taboo words.

The result of the process is a series of fully labelled images. An image is described as being ``fully labelled" when it meets the following criteria:
\begin{itemize}
\item users can no longer agree on a valid term to describe the image.
\item the majority of users are no longer able to provide a suitable label and instead choose to pass when the image is displayed.
\end{itemize}

\begin{figure}
\centering
 \includegraphics[width=80mm]{gameScreenShot.eps}
 \caption{Screen shot of the labelling game}
\end{figure}




\subsection{General Description of CAPTCHA System}

The CAPTCHA proposed here requires a user to match an image with a selected term.  An example of this process would be for six images to be displayed: An eye, a person jumping, Batman, a flower and a pizza.  A term is also displayed in the case of the example this would be ``Eye"  this term is chosen from the highly frequent terms used to describe one of the images displayed.  To correctly  verify that the user is not an automated process. The user must match the term to the image which it describes, in this case the selection of the picture of the eye would be the correct answer.  The system provides  accessibility` to blind users though assigning a term a which is representative of each image displayed by the CAPTCHA. The label is located in the image's HTML alt tags, which is verbalised by the user's screen reader.  We surmise that the relationship between the matching term and the term assigned to the image will provide enough information to the user, while still constituting a significantly challenging artificial intelligence problem.

Therefore, if the term to match was ``Eye" then ``Retina" would be an appropriate associated word.  As the terms are read by the user's own screen reader we surmise that this will overcome the usability problems associated with distorted sounds used by audio CAPTCHAs.  The screen reader provides clear and familiar feedback. A live version of the system can be found at \url{http://www.blindcaptcaha.co.uk}.  Figure \ref{fig_screenshotimages} displays the system with the images, while \ref{fig_screenshotnoimages} is a text only display which displays the information read by the screen reader.


It must not be possible for two images to appear on the CAPTCHA which could match the provided term.  To mitigate this problem, the system must only use images which we describe as being ``fully labelled".  We define an image as being fully labelled when there are no more previously unknown terms which can be assigned to an image(See section \ref{subsec_generatelabels} for on how the system determines that an image is fully labelled).  This is to prevent an image which could be described by a label, that has not been added at the time of the pictures introduction into the CAPTCHA.  


A distinction is made between the terms which can be used as matching terms and those used by blind user's to determine if the images are associated to the matching term.  This is based on a zipfian distribution of the terms(see section \ref{sec_dist} for how the terms were distributed in this way) used to describe the images.  This means that the most frequent term used to describe an image will occur approximately twice as often as the second most frequent term.  The terms need to be chosen from the high frequency terms while the image labels are taken from the most descriptive terms\cite{zipfslaw}.  This still provides the user with enough information to make the connection between the two terms, without providing so much information that a bot could extrapolate the association between the words.

\begin{figure}[h]\label{fig_overallarchitecture}
\centering
 \includegraphics[width=80mm]{ArchitectureDiagram.eps}
 \caption{The overall architecture of the solution}
\end{figure}


The selection process for the matching terms is as follows:  
\begin{itemize}
\item a random image is selected
\item a frequently-used term to describe the image is selected. This is the term which has to be matched
\item a less frequent term used to describe the image is also selected; this will be placed in the images alt tag
\item five other images and related terms are randomly chosen and added to the list
\item the order of the list of images and terms is randomised. This is to prevent the order of the images from revealing the matching image.
\end{itemize}  

The current configuration of the CAPTCHA is set up to test the CAPTCHA's usability.  To determine the usability of the system the following metrics are collected: 
\begin{itemize}
\item the amount of time taken for the user to complete each CAPTCHA
\item the term the user has to match the image to
\item the images and terms which consist of the wrong answers
\end{itemize}


\begin{figure}[h]\label{fig_screenshotimages}
\centering
 \includegraphics[width=80mm]{captchaWithImages.eps}
 \caption{Screen shot of the KAPTCHA system, with images}
\end{figure}

\begin{figure}[h]\label{fig_screenshotnoimages}
\centering
 \includegraphics[width=80mm]{captchaWithoutImages.eps}
 \caption{Screen shot of the KAPTCHA system, what is seen by the screen reader}
\end{figure}






\subsection{Attack of the System}\label{subsect_attacksystem}
The best method to attack the proposed CAPTCHA is to test the level of association between the matching term and the labels which describe an image labels.  For example if the matching term was Afro and the labels were: Falcon, Disney, Style, Rink, Gun and Space,  the answer is ``Style".  For an automated process to determine if two terms have a high level of association, the program would require a frame of reference which it could make inference on the level of association.  To provide a frame of reference the program would select a highly relevant document on the topic of the matching term.  As the terms which are not the correct answer are not related to the matching term they are less likely to be present in a highly relevant document about an unassociated term.  For this purpose Wikipedia \footnote{\url{http://www.wikipedia.com}} articles were utilised to provide the highly relevant documents.  From the point of view of a spammer an attack is considered successful if the following conditions are met:
%This  is probably bull
\begin{itemize}
\item the relevant document contains only one of the labels.
\item the time taken for the attack to be completed is significantly longer than its completion by a human.
\item the label is the correct answer.
\end{itemize}
Meeting this criteria the system would provide a false positive by verifying that the automated process was a human entity.


\begin{algorithm}[H]\label{algor_attack}
\SetLine
var doc a highly relevant document returned by a query consisting of the matching term\;
var numLabels the number of labels which occur in doc\;
var listLabels a list of the six images label from the CAPTCHA\; 
var currentLabel initially set to the first item in listLabels\;
var possibleSolutions emoty list which contains the possible correct terms\;
\While{not at end of CAPTCHA labels}{
\If{doc contains currentLabel}{
	add currentLabel to possibleSolutions\;
}
	set currentLabel to next in list\;
}
\Return possibleSolutions\;
\caption{Pseudocode of the attack process}
\end{algorithm}



This algorithm is not intended as a proof of the level of the security KAPTCHA provides, its purpose is to test what I consider the weakest link in the security. Although there may be numerous possible attacks which could successfully be performed to break KAPTCHA.   It is not possible to be able to determine the level of security KAPTCHA provides until it has been subjected to a rigorous peer review\cite{weaksecurity}.
